package interview;

public class interview_17_24 {
    public int[] getMaxMatrix(int[][] matrix) {
        int m=matrix.length;
        int n=matrix[0].length;
        int max = Integer.MIN_VALUE;
        int[] result=new int[4];
        for(int i=0;i<m;++i){
            int[] tmp = new int[n];
            for(int j=i;j<m;++j){
                for(int k=0;k<n;++k){
                    tmp[k]+=matrix[j][k];
                }
                int[] turn =arrayMax(tmp);
                if(max<=turn[2]){
                    max=turn[2];
                    result[0]=i;
                    result[1]=turn[0];
                    result[2]=j;
                    result[3]=turn[1];
                }
            }
        }
        return result;
    }
    public int[] arrayMax(int[] array){
        int len=array.length;
        int max=array[0];
        int left=0;
        int right=0;
        int sum=0;
        int left_return=0;
        int right_return=0;
        while(right<len){
            sum+=array[right];

            if(max<sum){
                max=sum;
                left_return=left;
                right_return=right;
            }
            if(sum<0){
                left=right+1;
                sum=0;
            }
            right++;
        }
        return new int[]{left_return,right_return,max};
    }
}
